#include <iostream>     // std::cout, std::cin
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <chrono>
#include "ej3.h"

using namespace std;


void mostrar_tablero(Tablero &t);
bool cruzConBlancos(Tablero &t, int posx, int posy);
bool fila_blancas(Tablero &t, int posx, int posy);
bool columna_blancas(Tablero &t, int posx, int posy);

Pieza::Pieza(int i): num(i)		//O(1)
{
  cin >> sup;
  cin >> izq;
  cin >> der;
  cin >> inf;
}


Tablero::Tablero()		//O(cant_rows*cant_cols)
{
  cin >> cant_rows;
  cin >> cant_cols;
  cin >> cant_colores;
  posiciones.resize(cant_rows);  //puede llegar a ser hasta O(cant_rows)
  
  for (int i = 0; i < cant_rows; i++)	//O(cant_rows)
  {
    posiciones[i].resize(cant_cols);	//O(cant_cols)
  }

  usadas.resize(cant_rows*cant_cols);
  cant_usadas = 0;
}

vector<Pieza> pedir_entrada(Tablero &t)	//O(sumatoria(de 1 hasta n*m)) = O((n*m)^2)
{
  vector<Pieza> piezas;

  for(int i = 0; i < (t.cant_rows*t.cant_cols); i++)
  {
    Pieza x = Pieza(i);
    piezas.push_back(x);   		//O(tam_arr hasta el momento)
  }

  return piezas;
}



bool cruzConBlancos(Tablero &t, int posx, int posy){
	if ((t.posiciones[posx][posy] == NULL) && (esTablero(t,posx-1,posy))){
		if (t.posiciones[posx-1][posy] == NULL){
			return (noEsTablero(t,posx-2,posy) && noEsTablero(t,posx-1,posy-1) && noEsTablero(t,posx-1,posy+1));
		}
	}
	return false;
}




vector<Pieza*> piezasCandidatas(Tablero &t, vector<Pieza> &piezas, int posx, int posy, int &cant)		// O(n_piezas)
{
  vector<Pieza*> candidatos;
    
  for(int i = 0; i < piezas.size(); i++)
  {
    if(t.usadas[i] == 0)
    {
      if(noEsTablero(t, posx-1, posy) || t.posiciones[posx-1][posy]->inf == piezas[i].sup)
      {
        if(noEsTablero(t, posx, posy-1) || t.posiciones[posx][posy-1]->der == piezas[i].izq)
        {
          candidatos.push_back(&piezas[i]);
          cant ++;
         }
      }   
    }
  }

  return candidatos;
}





bool esTablero(Tablero &t, int posx, int posy){	// O(1)
	//si estoy dentro de los limites del tablero
  return ((posx >= 0)&& (posy >= 0) && (posx < t.cant_rows) && (posy < t.cant_cols)) ;
 }




bool noEsTablero(Tablero &t, int posx, int posy){	// O(1)
	//si estoy fuera de los limites del tablero o es una ficha comodín(NULL)
  if(posx < 0 || posy < 0 || posx >= t.cant_rows || posy >= t.cant_cols || t.posiciones[posx][posy]==NULL){return true;} 
  return false;  
}


bool fila_blancas(Tablero &t, int posx, int posy){
		
	if (posx==0)//si estoy en la primera fila, definitivamente basta con una fila blanca
	{
		for(int i=0; i<t.cant_cols; i++)
		{
			if(t.posiciones[posx][i] != NULL)
			return false;
		}
		return true;
	}
	else//si no estoy en la primera fila, devuelvo verdadero si hay dos filas juntas
	{
		for(int j=0; j<2; j++){
			for(int i=0; i<t.cant_cols; i++){
			if(t.posiciones[posx-j][i] != NULL)
			return false;
			}
		}
		return true;
	}
}


bool columna_blancas(Tablero &t, int posx, int posy){
		
	if (posy==0)//si estoy al final de la primera columna, definitivamente basta con una columna blanca
	{
		for(int i=0; i<t.cant_rows; i++)
		{
			if(t.posiciones[i][posy] != NULL)
			return false;
		}
		return true;
	}
	else//si no estoy en la primera columna, devuelvo verdadero si hay dos columnas blancas juntas
	{
		for(int j=0; j<2; j++){
			for(int i=0; i<t.cant_rows; i++){
			if(t.posiciones[i][posy-j] != NULL)
			return false;
			}
		}
		return true;
	}
}

	
bool recursion(Tablero &t, Tablero &t_opt, vector<Pieza> &piezas, int posx, int posy){


  
  if (posy == t.cant_cols)// Si estoy al final de la fila paso a la proxima
  {
    posx += 1;
    posy =  0;
  }

  //si estoy al final, me fijo:
  if(posx == t.cant_rows)
  {
    if (piezas.size()==t.cant_usadas) // Si se completo devuelvo true y termino
    {
      return true;
    }
    else
    {         
      if(t_opt.cant_usadas < t.cant_usadas) //sino chequeo si cubre mas piezas
      {
      	t_opt=t;
      }
      return false;
    }
  }

  
  
  int posiciones_libres = piezas.size() - ((posx*t.cant_cols) + posy);	//O(1)
  int cantidad_max_posible = t.cant_usadas + posiciones_libres;		//O(1)
  
  //poda 1: si es en vano continuar para una mejor solucion
  if(cantidad_max_posible < t_opt.cant_usadas) //si se que no voy a encontrar una solucion mejor ya no sigo y corto la recursion
  {
    return false;
  }
  
  //if(cruzConBlancos(t,posx_aux,posy_aux))	//si el tablero forma alguna cruz con casillas blancas, seguro no es una solucion optima
  //{
//	  return false;
  //}
  
  vector<Pieza*> candidatos;
  int tam = piezas.size();
  candidatos.resize(tam);			//O(n)
  int cant_candidatas = 0; 
  candidatos = piezasCandidatas(t, piezas, posx, posy, cant_candidatas);       //O(n_piezas)
  
  for (int i = 0; i < cant_candidatas; i++)
  { 
    t.posiciones[posx][posy] = candidatos[i];
    t.usadas[candidatos[i]->num] = 1;
    t.cant_usadas += 1;
   
       
    if(recursion(t,t_opt, piezas, posx, posy+1))
    {
      return true;
    } 
     
    /*si no, la saco para poder probar otra combinacion*/
    t.posiciones[posx][posy] = NULL;
    t.usadas[candidatos[i]->num] = 0;
    t.cant_usadas -= 1;
  }
  
  //Poda 2: Pone un espacio vacio y sigue buscando, pero ya no puede devolver true
    if(cruzConBlancos(t,posx,posy))	//si el tablero forma alguna cruz con casillas blancas, seguro no es una solucion optima
  {
	  return false;
  }
  
	//poda 3: si encuentra una fila blanca al comienzo o dos filas blancas seguidas, corta recursion
	if (posy == (t.cant_cols-1))
	{	if (fila_blancas(t,posx,posy))
		return false;
	}
  
  
	//poda 4: si encuentra una columna blanca al comienzo o dos columnas blancas seguidas, corta recursion
	if (posx == (t.cant_rows-1))
	{	if (columna_blancas(t,posx,posy))
		return false;
	}
	
  recursion(t,t_opt, piezas, posx, posy+1);
  
  return false;
}



bool backtracking(Tablero &t, vector<Pieza> &piezas)
{ 
  Tablero t_optimo = t;

  //si encuentra una solucion devuelve true
  


    if(recursion(t,t_optimo, piezas, 0, 0)){return true;}
    
  

  // si no, t_optimo tiene la optima que utiliza mas piezas
  t=t_optimo;
  return false;
}


//para la complejidad,  cant_rows=n y cant_cols=m
int main()
{
  Tablero t = Tablero();	//O(n*m)

  vector<Pieza> piezas = pedir_entrada(t);		//O((n*m)^2)
  auto start = chrono::high_resolution_clock::now();
  bool sol = backtracking(t, piezas);
  auto finish = chrono::high_resolution_clock::now();
  cout << chrono::duration_cast<chrono::microseconds>(finish - start).count() << endl;
  mostrar_tablero(t);


  return 0;
}





void mostrar_tablero(Tablero &t){
  for(int i = 0; i < t.cant_rows; i++)
  {
    for(int j = 0; j < t.cant_cols; j++)
    { 
      if(t.posiciones[i][j]!=NULL)
      {
	      cout << t.posiciones[i][j]->num+1 << " ";
	    }
	    else
      {
	      cout << "0 ";
	    }
    }
    cout << endl;
  }
  cout << endl << endl;
}













